package com.ljy.my_study.leetcode.丑数II;

import java.util.PriorityQueue;
import java.util.Queue;

/** 
* @author James
* @date 2018年9月19日 
*/
public class TestMain3 {

	public static void main(String[] args) {
		TestMain3 testMain3=new TestMain3();
		System.out.println(testMain3.nthUglyNumber(9));
	}
	
	public int nthUglyNumber(int n) {
		if(n==1) {
			return 1;
		}
		int[] arr= {2,3,5};
		Queue<Long> queue=new PriorityQueue<>();
		queue.add(2L);
		queue.add(3L);
		queue.add(5L);
		int count=1;
		Long num=null;
		while(count<n) {
			num=queue.poll();
			for(int i=0;i<arr.length;i++) {
				Long newNum=num*arr[i];
				if(!queue.contains(newNum)) {
					queue.offer(num*arr[i]);
				}
			}
			count++;
		}
		return num.intValue();
	}
	
	public int nthUglyNumber2(int n) {
        // write your code here
        Queue<Long> choushu = new PriorityQueue<>();
        if(n==1)
            return 1;
        choushu.offer((long)1);
        int[] factor = {2,3,5};
        for(int i=2;i<=n;i++){
            long num = choushu.poll();
            for(int f : factor){
                long tmp = f * num;
                if(!choushu.contains(tmp))
                    choushu.offer(tmp);
            }
        }
        return choushu.poll().intValue();
    }
}
